#include "List.cpp"

/*
 * 给你一个链表，每k个节点一组进行翻转，请你返回翻转后的链表。

k是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是k的整数倍，那么请将最后剩余的节点保持原有顺序。

进阶：

你可以设计一个只使用常数额外空间的算法来解决此问题吗？
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

 */

// 1 2 3 -> 4 5 6
// 3 2 1 -> 4 5 6
List ReverseK(List list,int k) {
    List head = (ListNode*) malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode* p = list;
    for (int i = 0; i < k; ++i) {
        ListNode *q = p->next;
        p->next = head->next;
        head->next = p;
        p = q;
    }
    return head->next;
}
// pre  p |q
// 1  2 3 |4 5 6 7 8 k=3

//         pos
//     p   pre  q
//  h  3 2 1 -> 6 5 4  7 8

List ReverseListWithK(List list,int k) {
    List head = (ListNode*) malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode* p = list;
    ListNode* pos = head;

    while(p != NULL) {
        ListNode* pre = p;
        for (int i = 0; i < k-1; ++i) {
            p = p->next;
            if (p == NULL) {
                pos->next = pre;
                return head->next;
            }
        }
        // 下次翻转的开始
        ListNode* q = p->next;
        // 翻转前K个元素
        ListNode* now = ReverseK(pre,k);
        // 并且将翻转过后的链表与当前while的head链接
        pos->next = now;
        for (int i = 0; i < k; ++i) {
            pos = pos->next;
        }
        p = q;
    }
    return head->next;
}

List Reverse(List list,int k) {
    List head = (ListNode*) malloc(sizeof(ListNode));
    ListNode* p = list;
    ListNode* pos = head;

    // 找到第K+1个元素
    for (int i = 0; i < k; ++i) {
        if (p == NULL) {
            return p;
        }
        pos->next = p;
        pos = pos->next;
        p = p->next;
    }
    ListNode* reverseList = ReverseK(head->next,k);
    head->next = reverseList;
    ListNode* q= reverseList;
    for (int i = 0; i < k-1; ++i) {
        q = q->next;
    }
    q->next = Reverse(p,k);
    return head->next;
}

int main() {
    int number[] = {1,2,3,4,5,6,7,8};
    List list = CreateListByArray(number, ARRAY_SIZE(number));
    List newList = ReverseListWithK(list,3);
    PrintList(newList);
}